/*
**********************************************************
*
* Programme :	menu.c
*
* ecrit par :	Najim Boujedli et Jeremy Paneri
*
* resume :		création et manipulation de liste doublement chaînée
* 
*
*
* date : 		26/02/13
*
***********************************************************
*/


/*
	creation
	lecture
	insertionSommet
	insertionArete
	suppressionSommet
	suppressionArete
	affichage
	sauvegarde
	quitter
*/

#include <stdio.h>
#include <stdlib.h>

#include "menu.h"
#include "typ.h"

#include "libcoord.h"
#include "libgraphe.h"
#include "libtas.h"
#include "algos.h"

int main(int argc, char**args) {
	if(argc < 3) {
		printf("USAGE : ./menu nombre_de_sommets graine_aleatoire\n");
		return -1;
	}

	int i, j;
	int nbSommets = atoi(args[1]);
	int graine = atoi(args[2]);

	if(nbSommets < 3) {
		printf("Le nombre de sommets doit être >=3.\n");
		return -1;
	}
	

	/* Préparation */

	// Initialisation du tableau
	TypCoord** tab = creerTableau(nbSommets, graine);

	printf("-- Tableau des sommets créés --\n");
	affichageTableau(tab, nbSommets);
	printf("\n");

	// Création du graphe
	TypGraphe* graphe = creerGraphe(nbSommets);
	for(i=1 ; i<nbSommets+1 ; i++) {
		insertionSommet(graphe, i);
	}

	// Complétion du graphe et calcul des poids
	printf("-- Calcul des poids des arêtes --\n");
	for(i=1 ; i<nbSommets+1 ; i++) {
		for(j=i+1 ; j<nbSommets+1 ; j++) {
			printf("(%d,%d)\t--> %f\n", i, j, calculDistance(tab[i-1], tab[j-1]));
	    	if(insertionArete(graphe, i, j, calculDistance(tab[i-1],tab[j-1]))==2) {
	    		printf("Erreur -- (%d,%d)\t--> %f\n", i, j, calculDistance(tab[i-1],tab[j-1]));
	    	}
		}
	}

	printf("\n-- Affichage du graphe --\n");
	
	sortieGraphe(NULL, graphe);

	printf("\n");

	
	/* Calculs */

	// Calcul de la solution optimale si N<10
	if(nbSommets < 15) {
		printf("-- N<10 : Solution optimale par énumération --\n");
		int* res = (int*) malloc(sizeof(int)*(nbSommets));
		
		double f_res = 0;
		int* lettres = (int*) malloc(sizeof(int)*(nbSommets));

		for(i=0;i<nbSommets;i++)
			lettres[i] = i+1;
		
		int* prefixe = (int*)calloc(sizeof(int),nbSommets);

		enumereCycles(prefixe, 0, lettres, nbSommets, graphe, res, &f_res);
		afficheTab(res,nbSommets);
		printf(" -> %f\n\n", f_res);
		free(lettres);
		free(prefixe);
		free(res);
		res = NULL;
	}

	// Plus proche voisin
	printf("-- Algorithme du plus proche voisin --\n");
	
	int cheminResInt[nbSommets];
	
	double distRes = plusProcheVoisin(graphe, nbSommets, cheminResInt);
	afficheTab(cheminResInt,nbSommets);
	printf("-> %f\n",distRes);
		
	// Plus petit détour
	printf("\n-- Algorithme du plus petit détour --\n");
	
	distRes = plusPetitDetour(graphe, nbSommets, cheminResInt);
	printf("Plus petit détour");afficheTab(cheminResInt,nbSommets);
	printf("-> %f\n",distRes);
	
	// Parcours ARPM
	printf("\n-- Algorithme du parcours d'ARPM --\n");

	distRes = parcours_arpm(graphe, nbSommets, cheminResInt);
	printf("cheminARPM ");afficheTab(cheminResInt,nbSommets);
	printf("---%f\n", distRes);

	// Christophides
	printf("\n-- Algorithme de Christofides --\n");
	
	christofides(graphe, nbSommets, cheminResInt, &distRes);

	/* Libération */
	supprimerGraphe(&graphe);
	supprimerTableau(&tab, nbSommets);

	return 0;
}
